package week_02;

import java.util.Arrays;

public class MergeKSortList_23_2_1 {

    public static void main(String[] args) {
        int N = 10;
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = i;
        }

        int[] arr1 = Arrays.copyOfRange(arr, 0, N / 2);
        int[] arr2 = Arrays.copyOfRange(arr, N / 2, N);
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) return null;

        if (lists.length == 1) {
            return lists[0];
        } else if (lists.length == 2) {
            return merge(lists[0], lists[1]);
        } else {
            int len = lists.length;
            Arrays.copyOfRange(lists, 1, 4);
            ListNode node1 = mergeKLists(Arrays.copyOfRange(lists, 0, len / 2));
            ListNode node2 = mergeKLists(Arrays.copyOfRange(lists, len / 2, len));
            mergeKLists(new ListNode[]{node1, node2});
        }
        return null;
    }

    private ListNode merge(ListNode node1, ListNode node2) {
        ListNode root = new ListNode();
        ListNode tail=root;
        ListNode p1 = node1;
        ListNode p2 = node2;
        printList(node1);
        printList(node2);
        while (p1 != null || p2 != null) {
            if (p1 == null) {
                tail.next = p2;
                break;
            }
            if (p2 == null) {
                tail.next = p1;
                break;
            }
            if (p1.val <= p2.val) {
                tail.next = p1;
                tail=tail.next;
                p1 = p1.next;
            } else {
                tail.next = p2;
                tail=tail.next;
                p2 = p2.next;
            }
        }
        printList(root);
        return root.next;
    }

    private void printList(ListNode node) {
        while (node != null) {
            System.out.printf(node.val + " ");
            node=node.next;
        }
        System.out.println();
    }
}
